{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**通用最佳实践回顾**\n",
    "\n",
    "- `std::multiset<Key>` 与 `std::set` 相同维护严格弱序，却允许重复元素，非常适合需保留排序同时统计重复次数的“袋（bag）”场景。\n",
    "- 插入、查找、删除复杂度均为 `O(log n)`；同值元素在树中顺序相邻，可通过 `equal_range`、`count` 快速获取频次。\n",
    "- 插入不会使现有迭代器失效，删除仅影响被移除的节点。批量删除重复值时，使用 `erase(range)` 或 `it = multiset.erase(it)` 确保迭代器安全。\n",
    "- `lower_bound` / `upper_bound` 支持范围遍历；结合 `extract`（C++17）可迁移节点或调整键值，同时保留元素内容。\n",
    "- 在滑动窗口统计中常与另一个 `std::multiset` 搭配，实现中位数/分位数的动态维护；通过 `balance` 操作保持两侧规模相差不超过 1。\n",
    "- 如果仅需 O(1) 计数或无序访问，可比较 `std::unordered_multiset` 或 `std::map<Key,int>`；若数据量小且排序开销可接受，`std::vector` + 排序亦是替代方案。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| 序号 | 工程场景                                  | 文件名                               | 说明要点                                                     | 可运行示例代码         |\n",
    "| ---- | ----------------------------------------- | ------------------------------------ | ------------------------------------------------------------ | ---------------------- |\n",
    "| 1    | 需要计数的有序集合（袋）                  | `multiset_bag_counts.cpp`            | 自动计数并保持排序；利用 `count`、`equal_range` 查看频次；演示批量删除同值 | 示例 1：有序袋与计数   |\n",
    "| 2    | 滑动窗口中位数/分位数（双 multiset 技巧） | `multiset_sliding_window_median.cpp` | 使用两个 `multiset` 维护窗口左右两侧；动态平衡尺寸以实时获取中位数 | 示例 2：滑动窗口中位数 |\n",
    "| 3    | 排队/排行榜允许重复分数                   | `multiset_leaderboard.cpp`           | 排行榜存放分数并允许重复；利用逆序遍历输出排名；通过 `equal_range` 查询同分用户 | 示例 3：重复分数排行榜 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 示例 1：有序袋与计数（multiset_bag_counts.cpp）\n",
    "- 示例 2：滑动窗口中位数（multiset_sliding_window_median.cpp）\n",
    "- 示例 3：重复分数排行榜（multiset_leaderboard.cpp）"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "name": "C++17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
